package com.base.dynamicprograming;

/**
 * 221. 最大正方形
 *
 * @author leon
 * @date 2021年12月13日 15:02
 */
public class MaximalSquare {

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == '0'){
                    dp[i][j] = 0;
                    continue;
                }
                if(i==0||j==0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;

                }
                res = Math.max(res,dp[i][j]);
            }
        }
        return res*res;

    }

    public static void main(String[] args) {
        System.out.println(new MaximalSquare().maximalSquare(new char[][]{{'0','1'},{'1','0'}}));
    }
}
